/* ************************************************************************
> File Name:     SqList.h
# Author:       
# mail:          
> Created Time:  2023年02月13日 星期一 20时11分41秒
> Description:   
 ************************************************************************/

#ifndef SQLIST_H
#define SQLIST_H
#define INIT_SIZE 100
#define INCTEMENT 20
#include <iostream>
#include <set>
using namespace std;
template <typename T>
class Sqlist {
private:
    /* 顺序表的定义 
    -*/
    T *elem; // 存储空间基址
    int size; // 当前顺序表的存储容量
    int length; // 当前顺序表的长度
public:
    Sqlist() = default; // 默认的构造函数
    bool Init_Sqlist(); // 初始化顺序表
    int GetSize(); // 获取顺序表的存储容量
    int Getlen(); // 获取顺序表的长度
    void Clear(); // 重置顺序表
    bool Empty(); //判断表是否为空
    bool index(int idx, T &elem); // 用于获取相应下标的元素
    int index(int idx); // 用与获取第一个相似元素的位置 
    void traverse(void (* print)(T &elem)); // 用于打印顺序表中的元素
    bool insert(T elem); // 用于在顺序表的最后添加元素 
    bool insert(int idx, T elem); // 用与在顺序表指定的位置添加元素 
    bool remove(T &elem); // 用于删除顺序表的最后一个元素 ?
    bool remove(int idx, T &elem); // 用于在顺序表的指定位置删除元素 ?
    void replace(int idx, T elem); //替换相应位置的元素
    T operator[](int idx); // 重载下标运算符
    Sqlist<T>& operator= (const Sqlist<T> &rhs); // 重载赋值运算符
    ~Sqlist(); // 重写顺序表的析构函数
};

/*
    这里用来实现上述类中成员函数的定义
 */
template <typename T>
bool Sqlist<T>::Init_Sqlist() {
    this -> elem = (T *)malloc(INIT_SIZE * sizeof(T));
    if (!this -> elem) {
        cerr << "Init Wrong!" << endl;
        return false;
    }
    this -> size = INIT_SIZE;
    this -> length = 0;
    return true;
}

template <typename T>
inline int Sqlist<T>::GetSize() {
    return this -> size;
}

template <typename T>
inline int Sqlist<T>::Getlen() {
    return this -> length;
}

template <typename T>
inline void Sqlist<T>::Clear() {
    this -> length = 0;
}

template <typename T>
inline bool Sqlist<T>::Empty() {
    if (this -> length == 0) {
        return true;
    }
    return false;
}

template <typename T>
bool Sqlist<T>::index(int idx, T &elem) {
    if (idx < 1 || idx > this -> length) {
        return false;
    }
    elem = this -> elem[idx - 1];
    return true;
}

template <typename T>
int Sqlist<T>::index(int idx)
{
    if(idx < 1 || idx > this -> length) return -1;
    return this -> elem[idx - 1];    
}

template <typename T>
void Sqlist<T>::traverse(void (* print)(T &elem)) {
    for (int i = 0; i != this -> length; i++) {
        /* code */
        print((this -> elem)[i]);
    }
    cout << endl;
}

template <typename T>
bool Sqlist<T>::insert(T elem) {
    if (this -> length == this -> size) {
        T *newelem = (T *)realloc(this -> elem, (this -> size + INCTEMENT) * sizeof(T));
        if (!newelem) {
            cerr << "Error allocating memory!" << endl; 
            return false;
        }
        this -> size += INCTEMENT;
        this -> elem = newelem;
    }
    (this -> elem)[this -> length] = elem;
    this -> length += 1;
    return true;
}

template <typename T>
bool Sqlist<T>::insert(int idx, T elem) {
    if (idx < 1 || idx > this -> length + 1) {
        return false;
    }
    if (this -> length == this -> size) {
        T *newelem = (T *)realloc(this -> elem, (this -> size + INCTEMENT) * sizeof(T));
        if (!newelem) {
            cerr << "Error allocating memory!" << endl; 
            return false;
        }
        this -> size += INCTEMENT;
        this -> elem = newelem;
    }
    for(int i = this -> length; i >= idx; i--) {
        (this -> elem)[i] = (this -> elem)[i - 1];
    }
    (this -> elem)[idx - 1] = elem;
    this -> length += 1;
    return true;
}

template <typename T>
bool Sqlist<T>::remove(T &elem) {
    if (this -> length == 0) {
        return false;
    }
    elem = (this -> elem)[--this -> length];
    return true;
}

template <typename T>
bool Sqlist<T>::remove(int idx, T &elem) {
    if (this -> length == 0) {
        return false;
    }
    if (idx < 1 || idx > this -> length) {
        return false;
    }
    elem = (this -> elem)[idx - 1];
    for (int i = idx - 1; i < this -> length - 1; i++) {
        (this -> elem)[i] = (this -> elem)[i + 1];
    }
    this -> length--;

    return true;
}

template <typename T>
T Sqlist<T>::operator[](int idx) {
    if (idx < 1 || idx > this -> length) {
        cerr << "subscript wrong!" << endl; 

    }
    return this -> elem[idx - 1];
}

template <typename T>
Sqlist<T>::~Sqlist() {
    free(this -> elem);
    this -> elem = nullptr;
    this -> size = 0;
    this -> length = 0;
}

template <typename T>
void print(T &elem) {
    cout << elem << " ";
}

template <typename T>
void Sqlist<T>::replace(int idx, T elem) {
    if(idx < 1 || idx > this -> length) {
        cout << "错误" << endl;
        return;
    }
    this -> elem[idx - 1] = elem;
}

template <typename T>
bool compare(T t1, T t2) {
    /* 其中T代表任意的类型 */
    if (t1 == t2) {
        return true;
    }
    return false;
}

template <typename T>
Sqlist<T>& Sqlist<T>::operator= (const Sqlist<T> & rhs)
{
    if(this == &rhs)
    {
        return *this;
    }
    Clear();
    for(int i = 1; i <= rhs.Getlen(); i++)
    {
        this.insert(rhs.index(i));
    }
    return *this;
}

template <typename T>
void Quick_Sort(Sqlist<T> &array, int Start_Index, int End_Index);

template <typename T>
Sqlist<T> intersectSqlist(Sqlist<T> &l1, Sqlist<T> &l2);

template <typename T>
Sqlist<T> mergeSqlist(Sqlist<T> &l1, Sqlist<T> &l2);

int isTrue(string str);

void MySqList();
#endif

